%0 Conference Proceedings
%4 sid.inpe.br/sibgrapi@80/2006/08.16.16.48
%2 sid.inpe.br/sibgrapi@80/2006/08.16.16.48.53
%@doi 10.1109/SIBGRAPI.2006.20
%T Fast and Easy Computation of Approximate Smallest Enclosing Balls
%D 2006
%A Martinetz, Thomas,
%A Madany Mamlouk, Amir,
%A Mota, Cicero,
%@affiliation Institute for Neuro- and Bioinformatics, University of L uebeck
%@affiliation Institute for Neuro- and Bioinformatics, University of L uebeck
%@affiliation Departamento de Matemática, Universidade Federal do Amazonas
%E Oliveira Neto, Manuel Menezes de,
%E Carceroni, Rodrigo Lima,
%B Brazilian Symposium on Computer Graphics and Image Processing, 19 (SIBGRAPI)
%C Manaus, AM, Brazil
%8 8-11 Oct. 2006
%I IEEE Computer Society
%J Los Alamitos
%S Proceedings
%K computational geometry, smallest enclosing ball, pattern recognition.
%X The incremental Badoiu-Clarkson algorithm finds the smallest ball enclosing n point in d dimensions with at least O(1/t^0.5) precision, after t iteration steps. The extremely simple incremental step of the algorithm makes it very attractive both for theoreticians and practitioners. A simplified proof for this convergence is given. This proof allows to show that the precision increases, in fact, even as O(u/t) with the number of iteration steps. Computer experiments, but not yet a proof, suggest that the u, which depends only on the data instance, is actually bounded by min{(2d)^0.5,(2n)^0.5}. If it holds, then the algorithm finds the smallest enclosing ball with epsilon precision in at most O(nd (d')^0.5 }/epsilon) time, with d=min{d,n}.
%@language en
%3 MotaC_SmallestEnclosingBalls.pdf